42  数据结构之列表

42.1 引言列表在数据管理中的核心地位

理论背景:动态数组的实现原理

Python列表(List)是基于动态数组(Dynamic Array)实现的顺序数据结构。从计算机科学的角度来看,列表的设计体现了空间与时间的精妙平衡:

  1. 连续内存存储: 列表元素在内存中连续存储,利用局部性原理(Locality Principle),提高CPU缓存命中率
  2. 自动扩容机制: 当空间不足时,列表会自动分配更大的内存块并复制元素,这种策略被称为超额分配(Over-allocation)
  3. amortized O(1): 虽然扩容操作本身是O(n),但由于扩容频率低,分摊到每次操作的平均时间复杂度为O(1)

数学分析:扩容策略的时间复杂度证明

Python列表的扩容采用几何增长策略。假设列表当前容量为N,当需要扩容时,新容量约为:

\[ N_{new} \approx N_{old} \times 1.125 + C \]

其中C是一个常数。这种策略确保了: - 扩容次数: 对于插入n个元素,最多需要\(O(\log n)\)次扩容 - 总复制成本: \(n + n/1.125 + n/1.125^2 + \cdots \approx n \times \frac{1}{1-1/1.125} \approx 9n\) - amortized cost: \(\frac{9n}{n} = O(1)\)

列表的四大核心特性:

特性 技术实现 时间复杂度 金融应用场景
可变性 元素可直接修改 O(1) 实时价格更新
有序性 维护插入顺序 - 时间序列数据
异构性 存储任意类型对象 - 混合数据记录
动态性 自动扩容 amortized O(1) 增量数据采集

补充说明:为什么Python列表扩容系数是1.125?

这个数值是经过精密计算的结果。较小的系数(如1.5)会浪费更多内存,较大的系数(如2.0)会增加扩容频率。Python的1.125(约9/8)在内存使用和性能之间达到了最优平衡。相比之下,Java ArrayList使用1.5,C++ std::vector通常使用2.0。

42.2 列表的基本操作

平台任务解答代码

以下代码与教学平台任务要求完全一致：

列表 42.1 
# 注：该代码块包含未完成的填空代码，需要在平台上完成
# 注意：此答案不全，请查阅平台。
# ⚠️ 平台原始代码 - 请原样输入至教学平台（注释除外），平台才会判定答案正确
#任务一
name_index = ["道琼斯工业平均指数","富时100指数","标普500指数","恒生指数","日经225指数","上证指数","深证指数"]  #创建指数名称列的列表
price_index = [41563.08,8376.63,5648.40,17989.07,38647.75,2842.21,8348.48]  # 定义列表price_index
 
print(name_index[2])        #访问 "标普500指数" 这个元素
 
print(price_index.index(8376.63))       #找出 8376.63 这个元素所在的索引值

#任务二
name_index = ["道琼斯工业平均指数","富时100指数","标普500指数","恒生指数","日经225指数","上证指数","深证指数"] 
price_index = [41563.08,8376.63,5648.40,17989.07,38647.75,2842.21,8348.48]  # 定义列表price_index
 
name_index.append("法国CAC40指数")         #按要求添加新元素
name_index.append("德国DAX指数")  # 将股指名称添加到列表
name_index.append("新加坡海峡指数")  # 将股指名称添加到列表
name_index.append("台湾加权指数")  # 将股指名称添加到列表
print(name_index)                   #打印添加新元素后的name_index列表
 
price_index.append(7630.95)         #按要求添加新元素
price_index.append(18906.92)  # 将股指收盘点数添加到列表
price_index.append(3442.93)  # 将股指收盘点数添加到列表
price_index.append(22268.09)  # 将股指收盘点数添加到列表
print(price_index)                 #打印添加新元素后的price_index列表


#任务三
name_index = ["道琼斯工业平均指数","富时100指数","标普500指数","恒生指数","日经225指数","上证指数","深证指数"] 
price_index = [41563.08,8376.63,5648.40,17989.07,38647.75,2842.21,8348.48]  # 定义列表price_index                         
 
price_index.remove(38647.75)  #删除"日经225指数"这个元素
                             
 
price_index.insert(6,2674.45)  #添加索引为6的"韩国综合指数"这个元素
print(name_index)  # 输出指数数据
print(price_index)  # 输出价格数据

#任务四
name_index = ["道琼斯工业平均指数","富时100指数","标普500指数","恒生指数","日经225指数","上证指数","深证指数"] 
price_index = [41563.08,8376.63,5648.40,17989.07,38647.75,2842.21,8348.48]  # 定义列表price_index
 
price_index.sort()     #将price_index列表元素由小到大排序
print(price_index)  # 输出价格数据

price_index.reverse()     #将price_index列表元素翻转
print(price_index)  # 输出价格数据

price_index.clear()  #删除price_index列表全部元素(使用clear函数)
print(price_index)  # 输出价格数据
列表 42.2 
# 创建列表:存储券商股票名称
# 方括号[]是列表的字面量语法
# 列表可以包含任意类型的对象,这里存储字符串类型的股票名称
stocks = ['中信证券', '国泰君安', '海通证券', '华泰证券']

# 访问元素:索引从0开始
# stocks[0]访问第一个元素,索引0指向列表的第一个位置
print('第一个:', stocks[0])  # 输出: 中信证券

# 负数索引:-1表示最后一个元素
# 这种语法糖简化了对列表末尾元素的访问
print('最后一个:', stocks[-1])  # 输出: 华泰证券

# 切片操作:[start:end],包含start,不包含end
# stocks[:3]等价于stocks[0:3],获取前3个元素(索引0,1,2)
print('前3个:', stocks[:3])  # 输出: ['中信证券', '国泰君安', '海通证券']

# stocks[1:4]获取索引1到3的元素(不包含索引4)
# 切片操作创建列表的浅拷贝,不会修改原列表
print('第2-4个:', stocks[1:4])  # 输出: ['国泰君安', '海通证券', '华泰证券']

# 修改元素:通过索引直接赋值
# 列表的可变性允许我们原地修改元素,而不需要创建新列表
stocks[1] = '申万宏源'  # 将索引1的元素从'国泰君安'改为'申万宏源'
print('\n修改后:', stocks)  # 输出修改后的完整列表

# 添加元素:append()方法在列表末尾添加元素
# append()的时间复杂度是amortized O(1),非常高效
stocks.append('招商证券')  # 在末尾添加'招商证券'
print('追加后:', stocks)  # 输出: ['中信证券', '申万宏源', '海通证券', '华泰证券', '招商证券']

# 删除元素:remove()方法删除第一个匹配的元素
# remove()需要先查找元素,时间复杂度为O(n)
stocks.remove('海通证券')  # 删除'海通证券'
print('删除后:', stocks)  # 输出: ['中信证券', '申万宏源', '华泰证券', '招商证券']

代码深度解析:

  1. 索引机制的内存模型:

    • Python列表存储的是对象的引用,而非对象本身
    • 每个引用占用8字节(64位系统)
    • 实际的字符串对象存储在堆内存的其他位置

  2. 切片操作的内存行为:

    # 切片创建新列表(浅拷贝)
sub_list = stocks[1:3]  # 创建新列表,包含对原对象的引用

# 修改原列表不影响切片
stocks[1] = '新券商'
# sub_list[1]仍然是'海通证券'

  3. append() vs insert() 性能对比: | 操作 | 时间复杂度 | 说明 | |——|———–|——| | append() | amortized O(1) | 在末尾添加,无需移动其他元素 | | insert(0, x) | O(n) | 在开头添加,需要移动所有元素 | | pop() | O(1) | 弹出末尾元素 | | pop(0) | O(n) | 弹出首元素,需要移动所有元素 |

  4. 金融应用:实时行情更新:

    # 模拟实时价格序列
prices = []  # 空列表,用于存储价格历史

# append()高效添加新价格
for new_price in [10.5, 10.6, 10.55, 10.7]:
    prices.append(new_price)

# 计算简单移动平均
# sum()和len()都是O(1)时间复杂度
avg_price = sum(prices) / len(prices)
print(f'平均价格: {avg_price:.2f}')

42.3 列表方法与时间复杂度分析

列表 42.3 
# 创建数值列表,用于演示各种列表方法
# 这个列表包含重复元素,便于演示count()方法
numbers = [3, 1, 4, 1, 5, 9, 2, 6]

# sorted()函数:返回排序后的新列表
# 原列表保持不变,sorted()使用Timsort算法,时间复杂度O(n log n)
# Timsort是归并排序和插入排序的混合算法,针对现实数据优化
numbers_sorted = sorted(numbers)
print('排序:', numbers_sorted)  # 输出: [1, 1, 2, 3, 4, 5, 6, 9]

# reverse()方法:原地反转列表
# 这是一个就地操作,不创建新列表,时间复杂度O(n)
numbers_sorted.reverse()  # 反转为降序
print('反转:', numbers_sorted)  # 输出: [9, 6, 5, 4, 3, 2, 1, 1]

# count()方法:统计元素出现次数
# 需要遍历整个列表,时间复杂度O(n)
print(f'计数(1): {numbers_sorted.count(1)}')  # 输出: 2 (数字1出现了2次)

# sum()函数:计算列表元素和
# 这是Python内置函数,时间复杂度O(n)
print(f'求和: {sum(numbers_sorted)}')  # 输出: 31 (9+6+5+4+3+2+1+1)

# len()函数:获取列表长度
# Python内部维护列表长度信息,时间复杂度O(1)
print(f'长度: {len(numbers_sorted)}')  # 输出: 8

# 列表推导式(List Comprehension):创建新列表的优雅方式
# 语法: [expression for item in iterable]
# 列表推导式比传统for循环更快,因为使用了字节码优化
squares = [x**2 for x in numbers_sorted]  # 计算每个元素的平方
print('平方:', squares)  # 输出: [81, 36, 25, 16, 9, 4, 1, 1]

易混淆概念辨析:sort() vs sorted()

方法 原地修改 返回值 使用场景
list.sort() 是 None 不需要保留原列表,节省内存
sorted(list) 否 新列表 需要保留原顺序 
# sort()方法示例
original = [3, 1, 2]
original.sort()  # 原地修改
print(original)  # [1, 2, 3]
# original变量指向的列表已被修改

# sorted()函数示例
original = [3, 1, 2]
new_list = sorted(original)  # 创建新列表
print(original)  # [3, 1, 2] - 原列表不变
print(new_list)  # [1, 2, 3] - 新列表排序

补充说明:Timsort算法的金融应用优势

Python的Timsort算法特别适合金融时间序列数据: 1. 自适应:对部分有序数据效率极高(接近O(n)) 2. 稳定排序:相等元素的相对顺序保持不变 3. 内存优化:对临时空间的需求很小

列表操作时间复杂度完整表:

操作 时间复杂度 说明
lst[i] O(1) 索引访问
lst.append(x) amortized O(1) 末尾追加
lst.insert(i, x) O(n) 任意位置插入
lst.pop() O(1) 弹出末尾
del lst[i] O(n) 删除任意位置
lst.remove(x) O(n) 删除指定值
x in lst O(n) 线性搜索
lst.index(x) O(n) 查找索引
len(lst) O(1) 获取长度
lst.sort() O(n log n) 排序

42.4 金融应用投资组合管理

列表 42.4 
# 定义持仓股票组合
# 这是一个包含字典的列表,每个字典代表一只股票的持仓信息
# 列表允许我们存储多个股票,字典允许每只股票有多个属性
portfolio = [
    {'code': '600519.SH', 'name': '贵州茅台', 'shares': 100, 'price': 1850.00},
    {'code': '000858.SZ', 'name': '五粮液', 'shares': 200, 'price': 220.50},
    {'code': '600036.SH', 'name': '招商银行', 'shares': 500, 'price': 45.20}
]

# 初始化总投资价值为0
total_value = 0

# 遍历投资组合中的每只股票
# for循环逐个访问列表中的元素(这里是字典)
for stock in portfolio:
    # 计算单只股票的持仓价值
    # stock['shares']获取持股数量
    # stock['price']获取股票价格(注意:原代码中第二项使用了'shares'键,可能是笔误)
    value = stock['shares'] * stock['price']

    # 累加到总投资
    # += 是增量赋值操作符,等价于 total_value = total_value + value
    total_value += value

    # 使用f-string格式化输出
    # stock['name']获取股票名称
    # :,.2f 表示格式化为带千分位的两位小数
    print(f"{stock['name']}: {value:,.2f}元")

# 输出总投资
# \n 是换行符
print(f'\n总投资: {total_value:,.2f}元')

代码深度解析:

  1. 列表+字典的数据结构设计:

    # 这种嵌套结构非常适合表示"实体-属性"关系
# 列表提供顺序和可变性,字典提供灵活的属性访问

# 等价的面向对象设计(需要先定义类)
class Stock:
    def __init__(self, code, name, shares, price):
        self.code = code
        self.name = name
        self.shares = shares
        self.price = price

# 对于简单数据结构,列表+字典更轻量
# 对于复杂行为,面向对象设计更合适

  2. 遍历模式的性能考量:

    # 方式1:直接遍历元素(本例使用)
for stock in portfolio:
    print(stock['name'])

# 方式2:遍历索引
for i in range(len(portfolio)):
    print(portfolio[i]['name'])

# 方式1更Pythonic,方式2在需要索引时使用

  3. 计算投资组合权重的扩展:

    # 计算每只股票的权重
weights = []
for stock in portfolio:
    value = stock['shares'] * stock['price']
    weight = value / total_value
    weights.append(weight)
    print(f"{stock['name']}: {weight:.2%}")

# 验证权重之和是否为1(或100%)
print(f'权重总和: {sum(weights):.4f}')  # 应该输出1.0000

  4. 实际应用:持仓分析:

    # 找出持仓价值最高的股票
max_value = 0
max_stock = None

for stock in portfolio:
    value = stock['shares'] * stock['price']
    if value > max_value:
        max_value = value
        max_stock = stock

print(f'最大持仓: {max_stock["name"]}, 价值: {max_value:,.2f}元')

列表的内存效率分析:

对于n个元素的列表: - 引用数组: n × 8字节(64位系统) - 对象开销: 每个对象约56字节(Python对象头) - 实际数据: 取决于对象内容

例如,包含1000个整数的列表: - 引用数组: 8 KB - 整数对象: 56 KB (1000 × 56) - 总计: 约64 KB

相比之下,NumPy数组只需约8 KB(紧凑存储),这正是科学计算使用NumPy的原因。

最佳实践总结:

  1. 选择列表的场景:
    • 需要频繁添加/删除元素
    • 元素类型不同
    • 需要保持插入顺序
    • 数据量较小(< 10,000个元素)
  2. 避免列表的场景:
    • 频繁在列表头部插入/删除 → 使用collections.deque
    • 需要快速查找 → 使用字典或集合
    • 大规模数值计算 → 使用NumPy数组
    • 需要频繁拼接字符串 → 使用str.join()
  3. 性能优化技巧:
    • 使用list.append()而非list + [x](后者创建新列表)
    • 使用列表推导式而非for循环
    • 预分配列表大小(如果已知):[None] * n
    • 使用extend()批量添加元素而非循环append()